package cn.djb.day9;

/**
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * <p>
 * 要求时间复杂度为O(n)。
 */
class Solution_2 {

    public int maxValue(int[][] grid) {

        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    if (j > 0) {
                        grid[i][j] += grid[i][j - 1];
                    }
                }
                if (j == 0) {
                    if (i > 0) {
                        grid[i][j] += grid[i - 1][j];
                    }
                }
                if (i > 0 && j > 0) {
                    grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
                }
            }
        }
        return grid[m - 1][n - 1];

    }

    /**
     * 优化：先处理第一列 和第一行
     *
     * @param grid
     * @return
     */
    public int maxValue2(int[][] grid) {

        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];

    }
}